Devise and analyze (in worst-case terms) a divide-and-conquer algorithm for the
following problem. Given a set of rectangles, all bases of which lie on the x-axis,
determine the upper envelope of the collection of rectangles.

Would your algorithm still work if the set contained triangles rather than rectangles (still with their base on the $x$-axis, of course)? How far can you generalize the types of shapes for which your algorithm will work?
\\\\

Let's first decide that upper envelope is represented as the sequence of points which are successively connected by linear segments. 

The divide and conquer algorithm will have the following structure:

\begin{figure}[h]
\lstset{language=C, tabsize=2, frame=none, numbers=left, basicstyle=\small}
	\begin{lstlisting}[language=C]
FindUpperEnvelope(RectangleSet S)
	if |S| = 1 then 
		return upper envelope of it /*it will be represented as the first down left point, then upper left point, upper right point, and finally down right point*/
	Divide randomly given set S into two equal parts S1 and S2
	E1 = FindUpperEnvelope(S1)
	E2 = FindUpperEnvelope(S2)
	return Merge(E1,E2) //Merge two found upper envelopes E1 and E2
	\end{lstlisting}
\end{figure}

To merge two given upper envelopes, we'll go consequently through the lists of their points. At each step we'll have the current last segment of constructed upper envelope, that is only from one of envelopes or it is from both of them.

In case when it is from both of them, we need to find the next point of splitting, going successively through both lists of points. When we'll find it, the upper envelope should go via that envelope that goes up from other envelope, or in other words turns left from the last common point with respect to another envelope.

In case when the last segment is from only one envelope, we can refer to this envelope as the chosen one, and the will be unchosen. We know the next segment of the chosen envelope will be also in the constructed upper envelope fully only if it is not intersected with any segment of the unchosen one. In case of intersection the part of chosen envelope before the intersection should go to the constructed upper envelope, and then we know that the part of the segment of the unchosen envelope should go to it. So after the intersection chosen and unchosen envelopes will switch. From the definition of upper envelopes and the given form of elements, we know that each successive pair of points in the envelope will be in order of non-decreasing abscissa (x-coordinate). So if the segment of the first envelope doesn't intersect any segment of the second envelope until the first segment of it such that its left point is on the right of the right point of the given segment for which we search the intersection, then this given segment of the first envelope cannot intersect with any other segment of the second envelope (they all will be on the right of it). Thus, we can successively go through the lists of segments of both envelopes checking their intersection. In case of intersection, we need to switch the envelopes. And in case of not intersection we need to go to the next segment in the envelope, for which we know that there will be not intersection for the current segment with any segments of the second envelope (that is in case when current segment of second envelope has its left point on the right of the right point of it).

This algorithm more strictly may be written in the following way:

\lstset{language=C, tabsize=2, frame=none, numbers=left, basicstyle=\small}
	\begin{lstlisting}[language=C]
	Merge(E1,E2) {
		the new merged upper envelope E = empty
		/*E.last will refer to the last element in E
		E.add (the leftmost point of E1 and E2)*/
		A = E1.first
		B = E2.first
	while (A.next != null && B.next != null)
	{
		if (A.next == null)
				{
					B = B.next
					E.add(B)	
					continue		
				}
		if (B.next == null)
		{
			A = A.next
			E.add(A)	
			continue		
		}

		if (A == E.last && B == E.last)
		{		
			if sin((E.last,A.next),(E.last, B.next))== 0
			{
				// means that next segments are collinear and we need to add the point closest to the last added E.last
				nextPoint = the closest point to E.last between A.next and B.next
				E.add(nextPoint);				
				A = nextPoint; //in case when A.next is closest, we just go to the next point in E_1, else we go to the found point, but the next after it remains the same					
				B = nextPoint; //analogously
				continue
			}

			//the next point in the constructed upper envelope will be added from the left one given upper envelopes
			if sin((E.last,A.next),(E.last, B.next)) > 0
				E.add(A.next);
			else
				E.add(B.next);
			A = A.next;
			B = B.next;	
		}
		else
		{		
			// means that the last added point is not on the intersection of two envelopes E_1 and E_2
				if segments (A, A.next) and (B, B.next) are intersected
				{
					//need to switch between two envelopes
					E.add(pointOfIntersection);
					A = pointOfIntersection ;
					B = pointOfIntersection;
				}
				else
				{
					if (B.next.x >= A.next.x)
						A = A.next;				
					else
						B = B.next;				
				}
		}
	}
	}
	return E
\end{lstlisting}


The step of merging, thus, takes linear time, as we need to go only once through the lists of points of given envelopes.

So overall algorithm takes $T(|S|)$ time satisfying the following recurrence equation: $$T(|S|) = 2 T\left( \frac{|S|}{2}\right) + O(|S|)$$

We know by Master Theorem, that the solution for this equation is $T(|S|) = O \left( |S| \log |S|\right) $, so that is the estimation of complexity that this algorithm takes.

\vspace{10pt}
Considering the case with triangles based on the $x$-axis:
In case when all of them follow the restriction that going to the next point we go not to the left only, then our algorithm works fine. This condition means that for any point of triangle $(x,y)$ the segment $\{(x,0),(x,y)\}$ is within the triangle, so it represents the piecewise-linear function. We can see that in this case the envelope we'll be also represented by piecewise-linear functions, so for any figures represented by piecewise-linear functions our algorithm will work well, but the complexity will be based not on the number of figures, but on the number of vertices they include.

In case when triangle doesn't follow this restriction, we cannot stop searching the intersection of segments in any moment and need to look through all rest segments. So our algorithm doesn't work in this case. The same is with polygons in common case (when they are not necessarily represented as piecewise-linear functions).







	
	
